//
//  Problem606.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/4/8.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 606. 根据二叉树创建字符串
 你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

 示例 1:

 输入: 二叉树: [1,2,3,4]
        1
      /   \
     2     3
    /
   4

 输出: "1(2(4))(3)"

 解释: 原本将是“1(2(4)())(3())”，
 在你省略所有不必要的空括号对之后，
 它将是“1(2(4))(3)”。
 示例 2:

 输入: 二叉树: [1,2,3,null,4]
        1
      /   \
     2     3
      \
       4

 输出: "1(2()(4))(3)"

 解释: 和第一个示例相似，
 除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
 */
@objcMembers class Problem606: NSObject {
    func solution() {
        var node = TreeNode(1)
        node.left = TreeNode(2)
        node.right = TreeNode(3)
        node.left?.left = TreeNode(4)
        
        print(tree2str(node))
        
        
        var node1 = TreeNode(1)
        node1.left = TreeNode(2)
        node1.right = TreeNode(3)
        node1.left?.right = TreeNode(4)
        print(tree2str(node1))
    }
    
    func tree2str(_ t: TreeNode?) -> String {
        if t == nil {
            return ""
        }
        if t?.left == nil, t?.right == nil {
            return String(t!.val)
        }
        var str = String(t!.val) + "(" + tree2str(t?.left) + ")"
        if t?.right != nil {
            str += "(" + tree2str(t?.right) + ")"
        }
        
        print(str)
        return str
    }
}
